{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implement a Queue - Using Two Stacks\n",
    "\n",
    "Given the Stack class below, implement a Queue class using **two** stacks! Note, this is a \"classic\" interview problem. Use a Python list data structure as your Stack."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Uses lists instead of your own Stack class.\n",
    "stack1 = []\n",
    "stack2 = []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution\n",
    "\n",
    "Fill out your solution below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Queue2Stacks(object):\n",
    "    \n",
    "    def __init__(self):\n",
    "        \n",
    "        # Two Stacks\n",
    "        self.stack1 = []\n",
    "        self.stack2 = []\n",
    "     \n",
    "    def enqueue(self,element):\n",
    "        \n",
    "        # FILL OUT CODE HERE\n",
    "        pass\n",
    "    \n",
    "    def dequeue(self):\n",
    "        \n",
    "        # FILL OUT CODE HERE\n",
    "        pass  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test Your Solution\n",
    "\n",
    "You should be able to tell with your current knowledge of Stacks and Queues if this is working as it should. For example, the following should print as such:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "RUN THIS CELL TO CHECK THAT YOUR SOLUTION OUTPUT MAKES SENSE AND BEHAVES AS A QUEUE\n",
    "\"\"\"\n",
    "q = Queue2Stacks()\n",
    "\n",
    "for i in xrange(5):\n",
    "    q.enqueue(i)\n",
    "    \n",
    "for i in xrange(5):\n",
    "    print q.dequeue()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Good Job!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
